package com.jack.leetcode.每日一题;

/*** 
 * @author zhangjie
 * @date 2020/4/23 21:17
 */
public class 硬币 {

    public static void main(String[] args) {
        int n = 5;
        System.out.println(waysToChange(n));
        n = 6;
        System.out.println(waysToChange(n));
        n = 10;
        System.out.println(waysToChange(n));
    }

    public static int waysToChange(int n) {
        int[] a = new int[n+1];
        a[0] = 1;
        int[] coins = {1,5,10,25};
        for(int coin:coins){
            for(int i = coin;i<=n;i++){
                a[i] = (a[i] + a[i-coin])%1000000007;
            }
        }
        return a[n];
    }
}
